package huaweiod.first;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * 【最大化控制资源成本】【100%通过率】【2022.11 Q4 新题】
 * Leetcode--Java--253. 会议室 II
 *
 * 2
 * 3 9 2
 * 4 7 3
 * 5
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-06-21
 */
public class A_2023_01_MaxControlCost {

    // 遍历所有时间点，看会议在不在里面
    public static int MaxMeetingRooms1(int[][] ranges) {
        HashSet<Integer> point = new HashSet<>();
        for (int i = 0; i < ranges.length; i++) {
            point.add(ranges[i][0]);
            point.add(ranges[i][1]);
        }
        int max = 0;
        for (Integer p : point) {
            int count = 0;
            for (int i = 0; i < ranges.length; i++) {
                if (ranges[i][0] <= p && p <= ranges[i][1]) {
                    count += ranges[i][2];
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }

    // 优先级队列排序,根据会议的结束时间排序，若下一个会议的开始时间在此队列之前则资源叠加
    public static int MaxMeetingRooms2(int[][] ranges) {
        // 开始时间排序
        Arrays.sort(ranges, (a, b) -> a[0] - b[0]);
        // 优先级队列（小根堆 - 存会议结束时间）
        PriorityQueue<Integer[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int result = 0;
        int tempResult = 0;
        for (int i = 0; i < ranges.length; i++) {
            while (!pq.isEmpty()) {
                Integer[] peek = pq.peek();
                // 开始时间大于前一个会议的结束时间，移除资源
                if (ranges[i][0] > peek[0]) {
                    Integer[] poll = pq.poll();
                    tempResult -= poll[1];
                } else {
                    break;
                }
            }
            tempResult += ranges[i][2];
            pq.add(new Integer[]{ranges[i][1], ranges[i][2]});
            result = Math.max(result, tempResult);
        }
        return result;
    }

    // test
    public static void main(String[] args) {
        System.out.println("--------------------");
        int[][] ranges = {{2, 3, 1}, {6, 9, 2}, {0, 5, 1}}; // 2
        System.out.println(MaxMeetingRooms1(ranges) + "---" + MaxMeetingRooms2(ranges));
        System.out.println("--------------------");
        int[][] range1 = {{3, 9, 2}, {4, 7, 3}}; // 5
        System.out.println(MaxMeetingRooms1(range1) + "---" + MaxMeetingRooms2(range1));
        System.out.println("--------------------");
        int[][] ranges2 = {{0, 5, 1}, {2, 4, 1}, {3, 7, 3}, {6, 9, 2}}; //5
        System.out.println(MaxMeetingRooms1(ranges2) + "---" + MaxMeetingRooms2(ranges2));
    }
}
